#include <iostream>
#include <string.h>

using namespace std;

typedef enum
{
    Link,
    Thread
} NodeTag;

class TreeNode
{
private:
    char data;            // 值
    TreeNode *leftChild;  // 左孩子
    TreeNode *rightChild; // 右孩子
    NodeTag lTag, rTag;   // 线索Tag

    friend class MyTree; // 树类
    friend class HuffmanTree;

public:
    TreeNode(char, TreeNode *, TreeNode *, NodeTag, NodeTag);
    TreeNode(char, TreeNode *, TreeNode *);
    ~TreeNode();

    void printNode();
};

class MyTree
{
private:
    TreeNode *root; // 根指针
    bool isThread;  // 线索二叉树标志

public:
    MyTree();               // 无参构造
    MyTree(const char[]);   // 构造函数
    MyTree(const MyTree &); // 拷贝函数
    //~MyTree();              // 析构函数

    void preOrderTraverse();              // 前序遍历
    void inOrderTraverse();               // 中序遍历
    void postOrderTraverse();             // 后序遍历
    int countLeaf();                      // 叶结点计数
    int countHeight();                    // 计算树的深度
    bool isThreadedTree();                // 判断是否为线索二叉树
    bool inOrderThreading();              // 线索化
    TreeNode &locateNode(const char &);   // 结点定位
    TreeNode &preNode(const TreeNode &);  // 获取前驱结点
    TreeNode &nextNode(const TreeNode &); // 获取后继结点
    TreeNode *CreateBiTree(const char[], int &i);
    TreeNode *CopyTree(TreeNode *);
    void preOrder(TreeNode *);
    void inOrderTraverse(TreeNode *);
    void postOrderTraverse(TreeNode *);
    int countLeaf(TreeNode *);
    int countHeight(TreeNode *);
    void inOrderThreading(TreeNode *);
    void Threading(TreeNode *, TreeNode *&);
    void preOrderLocate(TreeNode *P, const char &, TreeNode *&);
    TreeNode *preNode(const TreeNode *);  // 获取前驱结点
    TreeNode *nextNode(const TreeNode *); // 获取后继结点
};

struct HuffmanNode
{
    int weight;
    int parent;
    int leftChild;
    int rightChild;
    string code;
    HuffmanNode() : weight(0), parent(-1), leftChild(-1), rightChild(-1), code("") {}
};

class HuffmanTree
{
private:
    HuffmanNode *mytree;
    int numNodes;
    int root;

    void CreateHuffmanTree(const int[], int);
    void GenerateCodes(int n);

public:
    HuffmanTree(const int &, const int[]); // 构造函数
    ~HuffmanTree();                        // 析构函数

    // 输出哈夫曼编码
    // 格式为：每行输出一个节点，节点排序递减
    // 节点1值：编码
    // 节点2值：编码
    //....
    // cpp中未给出该函数，遵守输出格式规范
    void printHuffmanCodes();
};
